package class_0919Trie2;
import java.util.HashMap;

public class Trie {
    // UTF-8 字符集范围较大，需要使用哈希映射存储各节点的后继
    private Node root; // 根节点

    // Trie 树节点的定义
    public static class Node {
        int pass; // 经过当前节点的字符串数量
        int end;  // 以当前节点结尾的字符串数量
        HashMap<Integer, Node> next = new HashMap<Integer, Node>(); // 存储从当前节点出发的路径
    }

    // Trie 树的构造函数，初始化根节点
    public Trie() {
        root = new Node();
    }

    /**
     * 查找 Trie 树中字符串 word 的出现次数
     * @param word 待查找的字符串
     * @return 返回 word 出现的次数
     */
    public int search(String word) {
        if (word == null) {
            return 0; // 若字符串为空，直接返回 0
        }
        Node cur = root;
        int len = word.length();
        // 从左到右遍历字符串的每个字符
        for (int i = 0, path; i < len; i++) {
            path = word.charAt(i); // 获取字符的 ASCII 编码
            if (cur.next.get(path) == null) {
                return 0; // 如果路径不存在，说明该字符串未插入过
            }
            cur = cur.next.get(path); // 沿路径继续向下走
        }
        return cur.end; // 若走到最后，返回字符串结尾的记录次数
    }

    /**
     * 将字符串 word 插入到 Trie 树中
     * @param word 待插入的字符串
     */
    public void insert(String word) {
        if (word == null) {
            return; // 无效字符串直接返回
        }
        Node cur = root;
        cur.pass++; // 根节点的 pass+1，表示有一个字符串经过根节点
        int len = word.length();
        // 从左到右遍历字符串的每个字符
        for (int i = 0, path; i < len; i++) {
            path = word.charAt(i); // 获取字符的 ASCII 编码
            if (cur.next.get(path) == null) {
                // 若当前字符路径不存在，新建一个节点
                cur.next.put(path, new Node());
            }
            cur = cur.next.get(path); // 进入下一个节点
            cur.pass++; // 经过该节点，pass 加 1
        }
        cur.end++; // 最后一个节点的 end 加 1，表示插入了该字符串
    }

    /**
     * 从 Trie 树中删除字符串 word
     * 若 word 未插入过，直接返回；若存在，则删除一次
     * @param word 要删除的字符串
     */
    public void delete(String word) {
        if (word == null || search(word) == 0) {
            return; // 若字符串为空或未插入过，直接返回
        }

        Node cur = root;
        cur.pass--; // 根节点的 pass 减 1
        int len = word.length();
        // 从左到右遍历字符串的每个字符
        for (int i = 0, path; i < len; i++) {
            path = word.charAt(i); // 获取字符的 ASCII 编码
            // 当前路径节点的 pass 减 1
            cur.next.get(path).pass--;
            if (cur.next.get(path).pass == 0) {
                // 若某节点的 pass 变为 0，则该路径后所有节点不再需要
                cur.next.put(path, null); // 直接删除该路径
                return;
            }
            cur = cur.next.get(path); // 继续向下遍历
        }
        cur.end--; // 字符串末节点的 end 减 1，表示减少一个字符串
    }

    /**
     * 返回以 prefix 为前缀的字符串数量
     * @param prefix 查询的前缀
     * @return 返回以 prefix 为前缀的字符串个数
     */
    public int prefixNumber(String prefix) {
        if (prefix == null) {
            return 0; // 无效前缀返回 0
        }
        Node cur = root;
        int len = prefix.length();
        // 从左到右遍历前缀的每个字符
        for (int i = 0, path; i < len; i++) {
            path = prefix.charAt(i); // 获取字符的 ASCII 编码
            if (cur.next.get(path) == null) {
                return 0; // 若某条路径不存在，说明没有字符串以该前缀开头
            }
            cur = cur.next.get(path); // 继续向下走
        }
        return cur.pass; // 返回以 prefix 为前缀的字符串数量
    }
}

